#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#include "assert.h"
#include "abb.h"
#include "key.h"
#include "data.h"
#include "bool.h"
#include "pila.h"
#include "tuple.h"
#include "cr.h"
#include "cw.h"

#define Leaf ((Tree) NULL)

struct sAbb {
	int cant;
	Tree t;
};

struct Branch {
	key k; data d;
	Tree l, r;
};

Abb abb_empty (void){
	Abb arbol;
	arbol = (Abb)calloc(1,sizeof(struct sAbb));
	arbol->cant = 0;
	arbol->t = Leaf;

	return arbol;
}

bool abb_is_empty (Abb arbol){
	return (arbol->cant == 0);
}

bool tree_is_empty (Tree arbol){
	return (arbol == Leaf);
}

key root (Tree arbol){
	key raiz;
	if (!tree_is_empty(arbol))
		raiz = arbol->k;
	else
		warnx("El arbol es vacio\n");
	return raiz;
}

Tree next (key k, Tree arbol){
	Tree siguiente;
	if (key_le(k,arbol->k))
		siguiente = arbol->l;
	else if (!key_le(k,arbol->k))
		siguiente = arbol->r;

	return siguiente;
}

Tree mk_leaf (key k, data d){
	Tree sub;

	sub = (Tree)calloc(1,sizeof(struct Branch));
	sub->k = key_clone(k);
	sub->d = data_clone(d);
	sub->l = Leaf;
	sub->r = Leaf;

	return sub;
}

void abb_add (Abb h, key k, data d){
	Tree p;

	if (abb_is_empty(h)){
		h->t = mk_leaf(k,d);
		h->cant = 1;
	}
	else {
		p = h->t;
		while(!tree_is_empty(next(k,p)) && !key_eq(k,root(p))){
			p = next(k,p);
		}
		if (key_le(k,root(p)))
			p->l = mk_leaf(k,d);
		else
			p->r = mk_leaf(k,d);

		h->cant = h->cant + 1;
	}
}

bool abb_exists (Abb h, key k){
	Tree p;

	p = h->t;
	while(!tree_is_empty(p) && !key_eq(k,root(p))){
		p = next(k,p);
	}

	return !tree_is_empty(p);
}

data abb_search (Abb h, key k){
	Tree p;

	p = h->t;
	while(!key_eq(k,root(p))){
		p = next(k,p);
	}

	return (p->d);
}

key max_k (Tree p){
	Tree q;

	q = p;
	while(q->r != NULL){
		q = q->r;
	}

	return q->k;
}

data max_d (Tree p){
	Tree q;

	q = p;
	while(q->r != NULL){
		q = q->r;
	}

	return q->d;
}

void delete_max (Tree p){
	Tree q, padre;

	q = p;
	if (p->r != NULL){
		while (q->r != NULL){
			padre = q;
			q = q->r;
		}
		q->d = data_destroy(q->d);
		q->k = key_destroy(q->k);
		padre->r = q->l;
		free(q);
	}
}

void abb_del (Abb h, key k){
	Tree q, p, s;
	key clave;
	data valor;
	q = h->t;

	if (key_eq(q->k,k) && q->l != NULL && q->r == NULL){
		q->k = key_destroy(q->k);
		q->d = data_destroy(q->d);
		p = h->t->l;
		free(h->t);
		h->t = p;
	}
	else if (key_eq(q->k,k) && q->l == NULL && q->r != NULL){
		q->k = key_destroy(q->k);
		q->d = data_destroy(q->d);
		p = h->t->r;
		free(h->t);
		h->t = p;
	}
	else if (key_eq(q->k,k) && q->l == NULL && q->r == NULL){
		q->k = key_destroy(q->k);
		q->d = data_destroy(q->d);
		free(h->t);
		h->t = NULL;
	}
	else{
		while (!key_eq(k,root(q))){
			p = q;
			q = next(k,q);
		}
		q->k = key_destroy(q->k);
		q->d = data_destroy(q->d);

		if (q->r == NULL && q->l != NULL){
			if (p->l == q)
				p->l = q->l;
			else
				p->r = q->l;
			free(q);
		}
		else if (q->l == NULL && q->r != NULL){
			if (p->l == q)
				p->l = q->r;
			else
				p->r = q->r;
			free(q);
		}
		else if (q->l == NULL && q->r == NULL){
			if (p->l == q)
				p->l = NULL;
			else
				p->r = NULL;
			free(q);
		}
		else {
			clave = max_k(q->l);
			valor = max_d(q->l);
			q->k = key_destroy(q->k);
			q->d = data_destroy(q->d);
			q->k = key_clone(clave);
			q->d = data_clone(valor);
			if (key_eq(clave,root(q->l))){
				q->l->k = key_destroy(q->l->k);
				q->l->d = data_destroy(q->l->d);
				s = q->l->l;
				free(q->l);
				q->l = s;
			}
			else {
			delete_max(q->l);
			}
		}
	}
	h->cant = h->cant-1;
}

int abb_length (Abb h){
	return (h->cant);
}

Abb abb_fromFile(char *nomfile){
	Abb arbol = abb_empty();

	tuple e;
	cr c;
	assert(nomfile!=NULL);
	c = cr_create(nomfile);
	cr_arr(c);
	while (!cr_fin(c)){
		e = cr_elec(c);
		abb_add(arbol,tuple_fst(e),tuple_snd(e));
		e = tuple_destroy(e);
		cr_av(c);
	}
	cr_destroy(c);
	return arbol;
}

void abb_toFile(char *nomfile, Abb h){
	Tree temp;
	stack pila;
	tuple e;
	cw c;

	assert(h != NULL);
	c = cw_create(nomfile);
	cw_arr(c);
	pila = empty();
	pila = push(pila,h->t);

	while (!is_empty_stack(pila)){
		temp = top(pila);
		pila = pop(pila);
		e = tuple_fromKeyData(temp->k,temp->d);
		cw_ins(c,e);
		e = tuple_destroy(e);
		if (temp->l != NULL){
			pila = push(pila,temp->l);
		}
		if (temp->r != NULL){
		pila = push(pila,temp->r);
		}
	}
	cw_destroy(c);
	free(pila);
}


void add_left_stack(Tree t,stack pila){
	Tree aux;

	aux = t;

	while(aux->l != Leaf){
		pila = push(pila, aux->l);
		aux = aux->l;
	}
}

void abb_pprint (Abb arbol){
	char *p, *pp;
	Tree aux;
	stack pila;

	pila = empty();
	pila = push(pila,arbol->t);
	add_left_stack(arbol->t,pila);

	while (!is_empty_stack(pila)){
		aux = top(pila);
		pila = pop(pila);
		p = (char*)calloc(key_lenght(root(aux))+1,sizeof(char));
		key_toString(root(aux),p);
		pp = data_toString(aux->d);
		printf("\n%s: %s \n \n",p,pp);
		free(p);
		free(pp);


		if(aux->r != Leaf){
			pila = push(pila,aux->r);
			add_left_stack(aux->r,pila);
		}
	}
	free(pila);
	pila = NULL;
}

Abb abb_destroy(Abb arbol){
	Tree temp;
	stack pila;
	pila = empty();
	pila = push(pila,arbol->t);

	while (!is_empty_stack(pila)){
		temp = top(pila);
		pila = pop(pila);
		if (temp != NULL){
		temp->k = key_destroy(temp->k);
		temp->d = data_destroy(temp->d);
		if (temp->l != NULL){
			pila = push(pila,temp->l);
		}
		if (temp->r != NULL){
			pila = push(pila,temp->r);
		}
		free(temp);
		}
	}
	free(arbol);
	arbol = NULL;
	free(pila);
	pila = NULL;
	return arbol;
}

